package repeatedSubstringPattern;

public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 暴力
//        for (int len = 1; len < s.length(); len++) {
//            if(s.length()%len==0) {
//                boolean bol = true;
//                for (int i = 0; i + len < s.length(); i++) {
//                    if(s.charAt(i) != s.charAt(i+len)) {
//                        bol = false;
//                        break;
//                    }
//                }
//                if(bol) {
//                   return true;
//                }
//            }
//        }
//        return false;
        // 字符串匹配 --- KMP算法
        // 在求出 next数组之后
        // 如果该字符串是重复的字串构成的字符串
        // 那么 假设 next[n] = k
        // next[k-1] = next[n] = k 即 next[n] = next[next[n]-1]
        // n-=next[k]
        return false;
    }
    private int[] getNext(String s) {
        int[] next = new int[s.length()];
        for (int i = 1,j=0; i < s.length(); i++) {
            while (j>0&&s.charAt(j)!=s.charAt(i)) {
                j = next[j-1];
            }
            if(s.charAt(j) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
